In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
, a
Turing degree
In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.
Overview
The concept of Turing degree is fund ...
'X''is high if it is computable in 0′, and the
Turing jump
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine w ...
'X''′is 0′′, which is the greatest possible degree in terms of
Turing reducibility
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to s ...
for the jump of a set which is computable in 0′.
Similarly, a degree is ''high n'' if its n'th jump is the (n+1)'st jump of 0. Even more generally, a degree d is ''generalized high n'' if its n'th jump is the n'th jump of the join of d with 0′.
See also
*
Low (computability) In computability theory, a Turing degree 'X''is low if the Turing jump 'X''′is 0′. A set is low if it has low degree. Since every set is computable from its jump, any low set is computable in 0′, but the jump of sets computable i ...
References
Computability theory
{{mathlogic-stub, date=February 2009